/*  slfdvpw2.cpp  by K.Tsuru  */
// funstion ID = 236    DRADIX, BRADIX
#ifndef SN_H
#include "sn.h"
#endif
/*******************************************************************
SLong and SInteger classes
It divides m by 2^p (< ULONG_MAX/radix) and puts into q,i.e.
q = m/(2^p). It returns the remainder. It is three over times faster
than a statement
    q = LsDiv(m, 1uL << p);
********************************************************************/
long LDivPow2(const SLong& m, SLong& q, uint p){
    if(p == 0){  q = m;     return 0;   }
    int mh = (int)m.Head(), mt = (int)m.Tail();
    ulong div = (p <= 2u*(uint)BRADIX_BITS) ? (1uL << p) : ULONG_MAX, div1 = div-1uL;
    if(div > m.SlOpMaxValue()) q.SetError(q.OUT_OF_RANGE, "LDivPow2", 236);
    int ms = m.Sign(236);
    if(mh <= 1){ //under two figures, including m = 0
        long r;
        q = LsDiv(m, div, &r);
        return r;
    }
//Pay attention to the case &m == &q.
    if(&m != &q){
        q.valloc(m.Size(), -1);
        if(mt) q.figure.clear(0, (uint)mt-1u);
        q.figure.clear((uint)mh+1u);
    }
    ulong rem = 0, u;       // rem : remainder
    ulong rdx = (ulong)m.Radix();
    const fType* mv = m.ReadFigures();
    fType* qv = q.figure.Elements();
#ifndef NDEBUG
m.figure(mh);
#endif

    for(int i = mh; i >= mt; i--) {
        u = (ulong)mv[i]+ rem*rdx;
        qv[i] = fType(u >> p);
        rem = u & div1;
    }
    if(rem){
        while(mt > 0){
            u = rem*rdx;
            mt--;   qv[mt] = fType(u >> p);
            rem = u & div1;
        }
    }
//It gets figure positions. mh > 0
    while(mh && !qv[mh]) mh--;  //a few times
    q.aHead = (uint)mh;
#ifndef NDEBUG
q.figure(mh);   q.figure(mt);
#endif
// 24 0000....0001 / 2 = 12 0000 ... 0000
    if(qv[mh]){ // q != 0
        while(!qv[mt]) mt++;
        q.SetSign(m.Sign());
    } else {    // q == 0
        mt = 0;     q.SetSign(0);
    }
    q.aTail = (uint)mt;
    return (long)ms*(long)rem;  //The reminder has the same sign as m.
}